package xin.yangshuai.leetcode01;

import java.util.*;

/**
 * LeetCodeLearn
 *
 * @author shuai
 * @date 2021/5/31
 */
public class LeetCodeLearn {
    public static void main(String[] args) {

        Map<Integer, Integer> map = new HashMap<>();
//        System.out.println(map.keySet().size() == 0);
//        System.out.println("------------");
        map.put(1, 1);
        map.put(2, 2);
//        System.out.println(map.get(3));
//        System.out.println(map.get(1));

        Solution solution = new Solution();

//        [1,2,3,4,5]
        //      2

        ListNode l1 = new ListNode(1
                , new ListNode(2
                , new ListNode(3
                , new ListNode(4
                , new ListNode(5
                , new ListNode(6
                , new ListNode(7
                , new ListNode(8
                , new ListNode(9
                , new ListNode(10
        ))))))))));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));


        char[][] board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}
                , {'6', '.', '.', '1', '9', '5', '.', '.', '.'}
                , {'.', '9', '8', '.', '.', '.', '.', '6', '.'}
                , {'8', '.', '.', '.', '6', '.', '.', '.', '3'}
                , {'4', '.', '.', '8', '.', '3', '.', '.', '1'}
                , {'7', '.', '.', '.', '2', '.', '.', '.', '6'}
                , {'.', '6', '.', '.', '.', '.', '2', '8', '.'}
                , {'.', '.', '.', '4', '1', '9', '.', '.', '5'}
                , {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};


        String a = "bcd" + 1 + 2 + 'A';
//        System.out.println(a);

        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};


//        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

//        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};

//        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};


        int[] nums = {1, 2, 0};

        int[][] intervals = {{1, 5}, {6, 8}};
        int[] newInterval = {5, 6};

        int[][] obstacleGrid = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};

        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};

        String str = "/../";


        String s = "ADOBECODEBANC";
        String t = "ABC";


        List<List<Integer>> combine = solution.combine(4, 2);


        char[][] matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};


        int i = solution.maximalRectangle(matrix);
        System.out.println(i);

        System.out.println(solution.intToRoman1(58));

        solution.divide1(-2147483648, 2);

        int[] array = {10, 1, 2, 7, 6, 1, 5};
        List<List<Integer>> list = solution.combinationSum2(array, 8);
        System.out.println(list);

        int i1 = solution.leastOpsExpressTarget(3, 19);
        System.out.println(i1);


    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Length = nums1.length;
        int nums2Length = nums2.length;

        int length12 = nums1Length + nums2Length;
        int[] ints = new int[length12];
        int k = 0;

        for (int item : nums1) {
            ints[k++] = item;
        }
        for (int value : nums2) {
            ints[k++] = value;
        }
        for (int i = 0; i < ints.length - 1; i++) {
            for (int j = i + 1; j < ints.length; j++) {
                int temp = ints[i];
                if (temp > ints[j]) {
                    ints[i] = ints[j];
                    ints[j] = temp;
                }
            }
        }

        double result = 0.0;
        int i = length12 / 2;
        if (length12 % 2 == 0) {
            result = ints[i] / 2d + ints[i - 1] / 2d;
        } else {
            result = ints[i];
        }
        return result;


    }


    public String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int max = 0;
        char[] maxArr = {chars[0]};
        for (int i = 0; i < chars.length; i++) {
            char temp = chars[i];
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[j] == temp) {
                    int m = i;
                    int n = j;
                    while (m < n) {
                        m++;
                        n--;
                        if (chars[m] != chars[n]) {
                            break;
                        }
                    }
                    if (m >= n) {
                        int t_max = j - i + 1;
                        if (t_max > max) {
                            max = t_max;
                            int a = 0;

                            maxArr = new char[t_max];
                            for (int k = i; k <= j; k++) {
                                maxArr[a++] = chars[k];
                            }
                        }
                    }
                }
            }
        }
        return String.valueOf(maxArr);
    }

    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        int cLength = chars.length;
        // 2*(numRows-1)为一组
        int line = ((cLength - 1) / (2 * (numRows - 1))) * (numRows - 1);
        int moreNum = ((cLength - 1) % (2 * (numRows - 1)));
        if (moreNum > numRows - 1) {
            int moreLine = moreNum % (numRows - 1);
            line = line + moreLine;
        }
        char[][] cArr = new char[numRows][line + 1];

        for (int i = 0; i < cLength; i++) {

            int line0 = (i / (2 * (numRows - 1))) * (numRows - 1);
            int moreNum0 = i % (2 * (numRows - 1));

            if (moreNum0 > numRows - 1) {
                int moreLine0 = moreNum0 % (numRows - 1);
                cArr[numRows - 1 - moreLine0][line0 + moreLine0] = chars[i];
            } else {
                cArr[moreNum0][line0] = chars[i];
            }
        }
        char[] char_n = new char[cLength];
        int i = 0;
        for (char[] chars1 : cArr) {
            for (char c : chars1) {
                if (c != 0) {
                    char_n[i++] = c;
                }
            }
        }
        return String.valueOf(char_n);
    }


    public int reverse(int x) {
        int n = 0;


        while (x != 0) {
            int i = x % 10;

            if (n > 214748364 || (n == 214748364 && i > 7)) {
                return 0;
            }
            if (n < -214748364 || (n == -214748364 && i < -8)) {
                return 0;
            }

            n = n * 10;
            n = n + i;
            x = x / 10;

        }
        return n;

    }

    public int myAtoi(String s) {

        char[] chars = s.toCharArray();
        int n = 0;
        boolean flag = true;
        boolean addFlag = true;
        for (char aChar : chars) {
            if (aChar >= 48 && aChar <= 57) {
                flag = false;

                int i = aChar - 48;

                if (!addFlag) {
                    i = -i;
                }

                if (n > 214748364 || (n == 214748364 && i > 7)) {
                    return 2147483647;
                }
                if (n < -214748364 || (n == -214748364 && i < -8)) {
                    return -2147483648;
                }


                n = n * 10 + i;


            } else if (aChar == ' ') {
                if (!flag) {
                    return n;
                }
            } else if (aChar == '+') {
                if (flag) {
                    flag = false;
                    addFlag = true;
                } else {
                    return n;
                }

            } else if (aChar == '-') {
                if (flag) {
                    flag = false;
                    addFlag = false;
                } else {
                    return n;
                }
            } else {
                return n;
            }

        }
        return n;
    }


    public boolean isPalindrome(int x) {


        if (x < 0) {
            return false;
        }

        int m = x;
        int n = 0;


        while (m != 0) {
            int i = m % 10;

            if (n > 214748364 || (n == 214748364 && i > 7)) {
                return false;
            }


            n = n * 10;
            n = n + i;
            m = m / 10;

        }
        return x == n;

    }


    public boolean isMatch(String s, String p) {


        // "mis*.i"

        /*
        1、
         */

        char[] pChars = p.toCharArray();
        List<Map<String, Integer>> list = new ArrayList<>();
        for (int i = 0; i < pChars.length; i++) {
            Map<String, Integer> map = new HashMap<>();
            if ('*' != pChars[i]) {
                if (i + 1 < pChars.length) {
                    if (pChars[i + 1] == '*') {
                        map.put("key", (int) pChars[i]);
                        map.put("flag", -1);
                        list.add(map);
                        i++;
                    } else {
                        map.put("key", (int) pChars[i]);
                        map.put("flag", 1);
                        list.add(map);
                    }
                } else {
                    map.put("key", (int) pChars[i]);
                    map.put("flag", 1);
                    list.add(map);
                }
            }
        }

        char[] sChars = s.toCharArray();

        int index = 0;

        int start = 0;
        int end = 0;

        for (int i = 0; i < list.size(); i++) {
            Map<String, Integer> map = list.get(i);
            if (map.get("flag") == 1) {
                if ('.' != map.get("key")) {
                    if ((int) sChars[index] == map.get("key")) {
                        index++;
                        continue;
                    } else {
                        return false;
                    }
                } else {
                    start = i;
                }

            } else {
                start = i;
            }

        }
        for (Map<String, Integer> map : list) {
            int key = map.get("key");
            System.out.println((char) key);
            System.out.println(map.get("flag"));
            System.out.println("----------------------");
        }
        return false;
    }


    public int maxArea(int[] height) {

        int maxArea = 0;
        int maxI = 0;
        int maxJ = 0;
        for (int i = 0, j = height.length - 1; i < j; ) {

            int currentI = height[i];
            int currentJ = height[j];

            int currentMin;

            if (currentI > currentJ) {
                currentMin = currentJ;
                j--;
                if (currentJ <= maxJ) {
                    continue;
                }
                maxJ = currentJ;
            } else {
                currentMin = currentI;
                i++;
                if (currentI <= maxI) {
                    continue;
                }
                maxI = currentI;
            }

            int currentArea = currentMin * (j - i + 1);

            maxArea = currentArea > maxArea ? currentArea : maxArea;
        }
        return maxArea;
    }

    public String intToRoman(int num) {

        int len = 0;
        String result = "";
        String[][] array = {{"I", "V"}, {"X", "L"}, {"C", "D"}, {"M"}};
        while (num > 0) {
            int more = num % 10;
            String result_temp = "";
            if (0 < more && more < 4) {
                int i = more % 5;
                while (i > 0) {
                    result_temp = result_temp + array[len][0];
                    i--;
                }
                result = result_temp + result;
            } else if (more == 4) {
                result = array[len][0] + array[len][1] + result;
            } else if (4 < more && more < 9) {
                int i = more % 5;
                while (i > 0) {
                    result_temp = result_temp + array[len][0];
                    i--;
                }
                result_temp = array[len][1] + result_temp;
                result = result_temp + result;
            } else if (more == 9) {
                result = array[len][0] + array[len + 1][0] + result;
            }
            len++;
            num = num / 10;
        }
        return result;
    }


    public int romanToInt(String s) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put((int) 'M', 1000);
        map.put((int) 'D', 500);
        map.put((int) 'C', 100);
        map.put((int) 'L', 50);
        map.put((int) 'X', 10);
        map.put((int) 'V', 5);
        map.put((int) 'I', 1);
        char[] chars = s.toCharArray();
        int result = 0;
        int nextValue = map.get((int) chars[0]);
        for (int i = 0; i < chars.length - 1; i++) {
            int current = nextValue;
            nextValue = map.get((int) chars[i + 1]);
            if (current < nextValue) {
                current = -current;
            }
            result = result + current;
        }
        result = result + map.get((int) chars[chars.length - 1]);
        return result;
    }

    public String longestCommonPrefix(String[] strs) {
        String result = "";
        int i = 0;
        String str = strs[0];
        while (true) {
            String s;
            boolean breakFlag = false;
            int length = str.length();
            if (i < length) {
                s = str.substring(i, i + 1);
            } else {
                break;
            }
            for (int j = 1; j < strs.length; j++) {
                String str1 = strs[j];
                int length1 = str1.length();
                if (i < length1) {
                    String s1 = str1.substring(i, i + 1);
                    if (!s1.equals(s)) {
                        breakFlag = true;
                        break;
                    }
                } else {
                    breakFlag = true;
                    break;
                }
            }
            if (breakFlag) {
                break;
            }
            i++;
            result = result + s;
        }
        return result;
    }

//    public List<List<Integer>> threeSum(int[] nums) {
//
//        List<List<Integer>> list = new ArrayList<>();
//
//        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
//
//        for (int i = 0; i < nums.length - 2; i++) {
//            for (int j = i + 1; j < nums.length - 1; j++) {
//                for (int k = j + 1; k < nums.length; k++) {
//                    if (nums[i] + nums[j] + nums[k] == 0) {
//
//                        int min = nums[i];
//                        int max = nums[i];
//                        if (nums[j] < min) {
//                            min = nums[j];
//                        }
//                        if (nums[k] < min) {
//                            min = nums[k];
//                        }
//                        if (nums[j] > max) {
//                            max = nums[j];
//                        }
//                        if (nums[k] > max) {
//                            max = nums[k];
//                        }
//
//                        Map<Integer, Integer> map1 = map.get(max);
//
//                        if (map1 == null || map1.get(min) == null) {
//                            List<Integer> integerList = new ArrayList<>();
//                            integerList.add(nums[i]);
//                            integerList.add(nums[j]);
//                            integerList.add(nums[k]);
//                            list.add(integerList);
//                            if (map1 == null) {
//                                Map<Integer, Integer> map2 = new HashMap<>();
//                                map2.put(min, 0 - min - max);
//                                map.put(max, map2);
//                            } else {
//                                map1.put(min, 0 - min - max);
//                            }
//
//                        }
//                    }
//                }
//            }
//        }
//        return list;
//    }

    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] > nums[j]) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[i] + nums[j] > 0) {
                    break;
                }
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] > 0) {
                        break;
                    }
                    if (k > j + 1 && nums[k - 1] == nums[k]) {
                        continue;
                    }
                    if (nums[i] + nums[j] + nums[k] == 0) {

                        List<Integer> integerList = new ArrayList<>();
                        integerList.add(nums[i]);
                        integerList.add(nums[j]);
                        integerList.add(nums[k]);
                        list.add(integerList);
                    }
                }
            }
        }
        return list;
    }

    public List<String> letterCombinations(String digits) {
        Map<String, String[]> map = new HashMap<>();
        map.put("2", new String[]{"a", "b", "c"});
        map.put("3", new String[]{"d", "e", "f"});
        map.put("4", new String[]{"g", "h", "i"});
        map.put("5", new String[]{"j", "k", "l"});
        map.put("6", new String[]{"m", "n", "o"});
        map.put("7", new String[]{"p", "q", "r", "s"});
        map.put("8", new String[]{"t", "u", "v"});
        map.put("9", new String[]{"w", "x", "y", "z"});

        char[] chars = digits.toCharArray();
        String[] letters = {};
        for (char aChar : chars) {
            String[] tempArray = map.get(String.valueOf(aChar));
            if (letters.length == 0) {
                if (tempArray != null) {
                    letters = tempArray;
                }
            } else if (tempArray != null) {
                String[] tempLetters = new String[letters.length * tempArray.length];
                int i = 0;
                for (String letter : letters) {
                    for (String temp : tempArray) {
                        tempLetters[i] = letter + temp;
                        i++;
                    }
                }
                letters = tempLetters;
            }
        }
        List<String> list = new ArrayList<>();
        for (String letter : letters) {
            list.add(letter);
        }
        return list;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        int i = 1;
        ListNode listNode = head;
        while (listNode.next != null) {
            i++;
            listNode = listNode.next;
        }
        int j = 1;
        if (i == n) {
            head = head.next;
        } else if (n < i) {
            listNode = head;
            while (j < i - n) {
                j++;
                listNode = listNode.next;
            }
            listNode.next = listNode.next.next;
        }
        return head;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode currentListNode1 = l1;
        ListNode currentListNode2 = l2;
        if (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                currentListNode1 = l2;
                currentListNode2 = l1;
            }
        } else if (l2 != null) {
            currentListNode1 = l2;
            currentListNode2 = l1;
        }
        ListNode headListNode = currentListNode1;
        ListNode previousListNode = null;
        while (currentListNode1 != null && currentListNode2 != null) {

            while (currentListNode1 != null && currentListNode1.val <= currentListNode2.val) {
                previousListNode = currentListNode1;
                currentListNode1 = currentListNode1.next;
            }
            previousListNode.next = currentListNode2;
            if (currentListNode1 == null) {
                break;
            }
            while (currentListNode2 != null && currentListNode2.val <= currentListNode1.val) {
                previousListNode = currentListNode2;
                currentListNode2 = currentListNode2.next;
            }
            previousListNode.next = currentListNode1;
            if (currentListNode2 == null) {
                break;
            }
        }
        return headListNode;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode l1 = lists[0];
        if (lists.length == 1) {
            return l1;
        }
        for (int i = 1; i < lists.length; i++) {
            ListNode l2 = lists[i];
            ListNode currentListNode1 = l1;
            ListNode currentListNode2 = l2;
            if (l1 != null && l2 != null) {
                if (l1.val > l2.val) {
                    currentListNode1 = l2;
                    currentListNode2 = l1;
                }
            } else if (l2 != null) {
                currentListNode1 = l2;
                currentListNode2 = l1;
            }
            ListNode headListNode = currentListNode1;
            ListNode previousListNode = null;
            while (currentListNode1 != null && currentListNode2 != null) {

                while (currentListNode1 != null && currentListNode1.val <= currentListNode2.val) {
                    previousListNode = currentListNode1;
                    currentListNode1 = currentListNode1.next;
                }
                previousListNode.next = currentListNode2;
                if (currentListNode1 == null) {
                    break;
                }
                while (currentListNode2 != null && currentListNode2.val <= currentListNode1.val) {
                    previousListNode = currentListNode2;
                    currentListNode2 = currentListNode2.next;
                }
                previousListNode.next = currentListNode1;
                if (currentListNode2 == null) {
                    break;
                }
            }

            l1 = headListNode;
        }
        return l1;
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        ListNode newHead = head.next;

        ListNode currentListNode = head;
        ListNode previousListNode = null;
        while (currentListNode != null) {
            ListNode nextListNode = currentListNode.next;
            if (nextListNode == null) {
                break;
            }
            currentListNode.next = nextListNode.next;
            nextListNode.next = currentListNode;
            if (previousListNode != null) {
                previousListNode.next = nextListNode;
            }
            previousListNode = currentListNode;
            currentListNode = currentListNode.next;

        }
        return newHead;

    }

    public ListNode reverseKGroup(ListNode head) {

        ListNode currentListNode = null;
        ListNode nextListNode = head;

        while (nextListNode != null) {
            ListNode temp = nextListNode.next;
            nextListNode.next = currentListNode;
            currentListNode = nextListNode;
            nextListNode = temp;
        }

        return currentListNode;
    }

    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode currentListNode = null;
        ListNode nextListNode = head;

        ListNode previousTail = null;
        ListNode currentTail = null;

        ListNode newHead = null;
        int i = 0;
        int j = 0;

        while (nextListNode != null) {
            while (nextListNode != null && i / k == j) {
                ListNode temp = nextListNode.next;
                if (i % k == 0) {
                    currentTail = nextListNode;
                    nextListNode.next = null;
                } else {
                    nextListNode.next = currentListNode;
                }
                currentListNode = nextListNode;
                nextListNode = temp;

                i++;
            }
            if (i / k == j) {
                nextListNode = currentListNode;
                currentListNode = null;
                while (nextListNode != null) {
                    ListNode temp = nextListNode.next;
                    nextListNode.next = currentListNode;
                    currentListNode = nextListNode;
                    nextListNode = temp;
                }
            }
            if (previousTail != null) {
                previousTail.next = currentListNode;
            }
            if (j == 0) {
                newHead = currentListNode;
            }
            j++;
            previousTail = currentTail;
        }
        return newHead;
    }

    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int len = nums.length;
        int j = 1;
        int a = nums[0];
        for (int i = 1; i < len; i++) {
            int b = nums[i];
            if (a == b) {
                length--;
            } else {
                nums[j] = b;
                a = b;
                j++;
            }
        }
        return length;
    }

    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int len = nums.length;
        int j = 0;
        for (int i = 0; i < len; i++) {
            int a = nums[i];
            if (a == val) {
                length--;
            } else {
                nums[j] = a;
                j++;
            }
        }
        return length;
    }

    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) {
            return 0;
        }
        int i = 0;
        char[] haystackArray = haystack.toCharArray();
        char[] needleArray = needle.toCharArray();
        while (i < haystackArray.length) {
            int j = i;
            int k = 0;
            while (j < haystackArray.length && k < needleArray.length && haystackArray[j] == needleArray[k]) {
                j++;
                k++;
            }
            if (k == needleArray.length) {
                return i;
            } else if (j == haystackArray.length) {
                return -1;
            }
            i++;
        }
        return -1;
    }

    public int divide(int dividend, int divisor) {
        if (dividend == -2147483648 && divisor == -2147483648) {
            return 1;
        }
        if (dividend == -2147483648 && divisor == -1) {
            return 2147483647;
        }
        if (dividend == -2147483648 && divisor == 1) {
            return -2147483648;
        }
        boolean flag = true;
        int more = 0;
        if (dividend == -2147483648) {
            dividend = 2147483647;
            more = 1;
            flag = false;
        }
        int count = 0;

        if (dividend < 0) {
            dividend = -dividend;
            flag = false;
        }
        if (divisor < 0) {
            divisor = -divisor;
            flag = !flag;
        }
        while (dividend - divisor >= 0 - more) {
            count += 1;
            dividend -= divisor;
        }
        if (flag) {
            return count;
        } else {
            return -count;
        }
    }

    public List<Integer> findSubstring(String s, String[] words) {

        Map<Integer, String> map = new HashMap<>();
        int i = 0;
        byte[] bytes = s.getBytes();
        int arrayLength = words.length;
        int step = 0;
        Map<String, Integer> wordMap = new HashMap<>();
        while (i < bytes.length) {
            for (int m = 0; m < words.length; m++) {
                String word = words[m];
                byte[] wordBytes = word.getBytes();
                if (i == 0) {
                    if (m == 0) {
                        step = wordBytes.length;
                    }
                    if (wordMap.get(word) != null) {
                        wordMap.put(word, wordMap.get(word) + 1);
                    } else {
                        wordMap.put(word, 1);
                    }
                }
                int j = i;
                int k = 0;
                while (j < bytes.length && k < wordBytes.length && bytes[j] == wordBytes[k]) {
                    j++;
                    k++;
                }
                if (k == wordBytes.length) {
                    map.put(i, word);
                }
            }
            i++;
        }
        Set<Integer> keySet = map.keySet();
        List<Integer> list = new ArrayList<>();
        for (Integer key : keySet) {
            int mapKey = key;
            int j;
            Map<String, Integer> tempWordMap = new HashMap<>();
            for (j = 0; j < arrayLength; j++) {
                if (map.get(mapKey) != null) {
                    String word = map.get(mapKey);
                    if (tempWordMap.get(word) != null) {
                        tempWordMap.put(word, tempWordMap.get(word) + 1);
                    } else {
                        tempWordMap.put(word, 1);
                    }
                    mapKey = mapKey + step;
                } else {
                    break;
                }
            }
            if (j == arrayLength) {
                int size = tempWordMap.entrySet().size();
                int count = 0;
                for (Map.Entry<String, Integer> entry : tempWordMap.entrySet()) {
                    if (entry.getValue().equals(wordMap.get(entry.getKey()))) {
                        count++;
                    } else {
                        break;
                    }
                }
                if (size == count) {
                    list.add(key);
                }
            }
        }
        return list;
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 1;
        for (; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
                int j = i + 1;
                for (; j < nums.length; j++) {
                    if (nums[j] <= nums[i - 1]) {
                        break;
                    }
                }
                int temp = nums[i - 1];
                nums[i - 1] = nums[j - 1];
                nums[j - 1] = temp;
                break;
            }
        }
        for (int j = i; j < nums.length - 1; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                if (nums[j] > nums[k]) {
                    int temp = nums[k];
                    nums[k] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                int offset = nums.length - i;
                int tempTarget = nums[i];
                for (int j = 0; j < nums.length; j++) {
                    int index = (i + offset) % nums.length;
                    int temp = nums[index];
                    nums[index] = tempTarget;
                    tempTarget = temp;
                    i = index;
                }
                return i;
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        boolean searchFirst = true;
        int[] result = {-1, -1};
        int i = 0;
        for (; i < nums.length; i++) {
            if (searchFirst) {
                if (nums[i] > target) {
                    break;
                } else if (nums[i] == target) {
                    result[0] = i;
                    searchFirst = false;
                }
            } else if (nums[i] > target) {
                break;
            }
        }
        if (!searchFirst) {
            result[1] = i - 1;
        }
        return result;
    }

    public int searchInsert(int[] nums, int target) {
        int i = 0;
        for (; i < nums.length; i++) {
            if (nums[i] >= target) {
                break;
            }
        }
        return i;
    }

    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            Map<Integer, Object> map0 = new HashMap<>();
            Map<Integer, Object> map1 = new HashMap<>();
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int cc = c;
                    if (map0.get(cc) != null) {
                        return false;
                    } else {
                        map0.put(cc, new Object());
                    }
                }
                char d = board[j][i];
                if (d != '.') {
                    int dd = d;
                    if (map1.get(dd) != null) {
                        return false;
                    } else {
                        map1.put(dd, new Object());
                    }
                }
            }
        }

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                Map<Integer, Object> map2 = new HashMap<>();
                for (int k = 0; k < 3; k++) {
                    int m = i * 3 + k;
                    for (int l = 0; l < 3; l++) {
                        int n = j * 3 + l;
                        char c = board[m][n];
                        if (c != '.') {
                            int cc = c;
                            if (map2.get(cc) != null) {
                                return false;
                            } else {
                                map2.put(cc, new Object());
                            }
                        }
                    }
                }
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {


        List<Map<String, Integer>> list = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if ('.' == board[i][j]) {
                    HashMap<String, Integer> map = new HashMap<>();
                    map.put("x", i);
                    map.put("y", j);
                    list.add(map);
                }
            }
        }

        Iterator<Map<String, Integer>> iterator = list.iterator();
        while (list.size() != 0) {
            while (iterator.hasNext()) {
                Map<String, Integer> next = iterator.next();
                Integer i = next.get("x");
                Integer j = next.get("y");

                Map<Integer, Object> map = new HashMap<>();
                int m = i / 3;
                int n = j / 3;
                for (int k = 0; k < 3; k++) {
                    int x = 3 * m + k;
                    for (int l = 0; l < 3; l++) {
                        if ('.' != board[i][3 * k + l]) {
                            int a = board[i][3 * k + l];
                            map.put(a, new Object());
                        }
                        if ('.' != board[3 * k + l][j]) {
                            int a = board[3 * k + l][j];
                            map.put(a, new Object());
                        }
                        int y = 3 * n + l;
                        if ('.' != board[x][y]) {
                            int a = board[x][y];
                            map.put(a, new Object());
                        }
                    }
                }
                if (map.size() == 8) {
                    for (int k = '1'; k < '9'; k++) {
                        if (map.get(k) == null) {
                            board[i][j] = (char) k;
                            iterator.remove();
                        }
                    }
                }
            }
        }
    }

    public String countAndSay(int n) {

        String result = "1";
        if (n == 1) {
            return result;
        }
        for (int i = 0; i < n - 1; i++) {
            char[] chars = result.toCharArray();
            int count = 0;
            char b = chars[0];
            result = "";
            for (char aChar : chars) {
                if (b == aChar) {
                    count++;
                } else {
                    result = result + count + b;
                    count = 1;
                    b = aChar;
                }
            }
            result = result + count + b;
        }
        return result;

    }

    public int trap(int[] height) {

        int a = 0;
        int b = height.length - 1;
        int c = 1;
        int count = 0;
        while (a <= b) {
            if (height[a] < c) {
                a++;
                continue;
            }
            if (height[b] < c) {
                b--;
                continue;
            }
            count = count + (b - a + 1);
            c++;
        }
        for (int ele : height) {
            count = count - ele;
        }
        return count;
    }


//    public List<List<Integer>> permute(int[] nums) {
//
//        for (int i = 0; i < 4; i++) {
//            for (int j = 0; j < 3; j++) {
//                for (int k = 0; k < 2; k++) {
//                    for (int l = 0; l < 1; l++) {
//                        for (int num : nums) {
//                            System.out.print(num + "、");
//                        }
//                        System.out.println();
//                    }
//
//                    sss(nums, 2);
//                }
//                sss(nums, 1);
//            }
//            sss(nums, 0);
//        }
//
//        return null;
//    }

    public void sss(int[] nums, int start) {

        int temp = nums[start];
        while (start < nums.length - 1) {
            nums[start] = nums[start + 1];
            start++;
        }
        nums[start] = temp;

    }

    public List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> list = new ArrayList<>();
        permute1(nums, nums.length, list);
        return list;

    }

    public void permute1(int[] nums, int length, List<List<Integer>> list) {

        if (length == 1) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            for (int num : nums) {
                arrayList.add(num);
            }
            list.add(arrayList);
        } else {
            for (int i = 0; i < length; i++) {
                permute1(nums, length - 1, list);

                int start = nums.length - length;
                int temp = nums[start];
                while (start < nums.length - 1) {
                    nums[start] = nums[start + 1];
                    start++;
                }
                nums[start] = temp;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        permuteUnique1(nums, nums.length, list);
        return list;
    }

    public void permuteUnique1(int[] nums, int length, List<List<Integer>> list) {

        if (length == 1) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            for (int num : nums) {
                arrayList.add(num);
            }
            list.add(arrayList);
        } else {
            Map<Integer, Object> map = new HashMap<>();
            for (int i = 0; i < length; i++) {
                int start = nums.length - length;
                if (map.get(nums[start]) == null) {
                    permuteUnique1(nums, length - 1, list);
                    map.put(nums[start], new Object());
                }

                int temp = nums[start];
                while (start < nums.length - 1) {
                    nums[start] = nums[start + 1];
                    start++;
                }
                nums[start] = temp;
            }
        }
    }

    public void rotate(int[][] matrix) {
        int length = matrix.length;
        int maxIndex = (length - 1) / 2;
        int num = length / 2 - 1;
        for (int i = 0; i <= num; i++) {
            for (int j = 0; j <= maxIndex; j++) {
                int temp = matrix[i][j];
                int x = i;
                int y = j;
                for (int k = 0; k < 3; k++) {
                    int preX = length - 1 - y;
                    int preY = x;
                    matrix[x][y] = matrix[preX][preY];
                    x = preX;
                    y = preY;
                }
                matrix[x][y] = temp;
            }
        }
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            byte[] bytes = str.getBytes();
            for (int i = 0; i < bytes.length - 1; i++) {
                for (int j = i + 1; j < bytes.length; j++) {
                    if (bytes[i] > bytes[j]) {
                        byte temp = bytes[i];
                        bytes[i] = bytes[j];
                        bytes[j] = temp;
                    }
                }
            }
            String key = new String(bytes);
            if (map.get(key) != null) {
                List<String> stringList = map.get(key);
                stringList.add(str);
            } else {
                List<String> stringList = new ArrayList<>();
                stringList.add(str);
                map.put(key, stringList);
                list.add(stringList);
            }

        }
        return list;
    }

    public int maxSubArray(int[] nums) {

        int count = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int tempCount = count + nums[i];
            if (nums[i] > tempCount) {
                count = nums[i];
            } else {
                count = tempCount;
            }
            max = max > count ? max : count;
        }
        return max;
    }

    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> list = new ArrayList<>();

        int xMaxIndex = matrix.length - 1;
        int yMaxIndex = matrix[0].length - 1;

        int x = 0;
        int y = 0;

        int xMinIndex = 0;
        int yMinIndex = 0;

        while (xMaxIndex >= xMinIndex && yMaxIndex >= yMinIndex) {

            for (; y < yMaxIndex; y++) {
                list.add(matrix[x][y]);
            }
            for (; x < xMaxIndex; x++) {
                list.add(matrix[x][y]);
            }
            if (x > xMinIndex) {
                for (; y > yMinIndex; y--) {
                    list.add(matrix[x][y]);
                }
            } else {
                list.add(matrix[x][y]);
                break;
            }
            if (y < yMaxIndex) {
                for (; x > xMinIndex; x--) {
                    list.add(matrix[x][y]);
                }
            } else {
                list.add(matrix[x][y]);
                break;
            }
            x++;
            y++;
            xMaxIndex--;
            yMaxIndex--;
            xMinIndex++;
            yMinIndex++;
            if (xMaxIndex == xMinIndex && yMaxIndex == yMinIndex) {
                list.add(matrix[x][y]);
                break;
            }
        }
        return list;
    }

    public boolean canJump(int[] nums) {
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] == 0) {
                int j = i;
                i--;
                for (; i >= 0; i--) {
                    if (i + nums[i] > j) {
                        break;
                    }
                }
                if (i < 0) {
                    return false;
                }
            } else {
                continue;
            }
        }
        return true;
    }

    public boolean canJump1(int[] nums) {
        int maxIndex = nums[0];
        for (int i = 0; i <= maxIndex; i++) {
            int tempMaxIndex = i + nums[i];
            maxIndex = maxIndex > tempMaxIndex ? maxIndex : tempMaxIndex;
            if (maxIndex >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

    public int[][] merge(int[][] intervals) {

        for (int i = 0; i < intervals.length - 1; i++) {
            for (int j = i + 1; j < intervals.length; j++) {
                if (intervals[i][0] > intervals[j][0]) {
                    int[] temp = intervals[i];
                    intervals[i] = intervals[j];
                    intervals[j] = temp;
                }
            }
        }

        List<int[]> list = new ArrayList<>();

        for (int i = 0; i < intervals.length; i++) {
            int[] range = intervals[i];
            int j = i + 1;
            for (; j < intervals.length; j++) {
                int[] tempRange = intervals[j];
                if (range[1] >= tempRange[0]) {
                    if (range[1] < tempRange[1]) {
                        range[1] = tempRange[1];
                    }
                } else {
                    break;
                }
            }
            i = --j;
            list.add(range);
        }
        int[][] array = new int[list.size()][2];
        int i = 0;
        for (int[] ints : list) {
            array[i] = ints;
            i++;
        }
        return array;
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {

        List<int[]> list = new ArrayList<>();
        boolean flag = true;
        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (flag) {
                if (interval[1] >= newInterval[0]) {
                    if (newInterval[1] < interval[0]) {
                        list.add(newInterval);
                    } else {
                        if (newInterval[1] > interval[1]) {
                            interval[1] = newInterval[1];
                        }
                        if (newInterval[0] < interval[0]) {
                            interval[0] = newInterval[0];
                        }
                        int j = i + 1;
                        for (; j < intervals.length; j++) {
                            int[] temp = intervals[j];
                            if (interval[1] >= temp[0]) {
                                if (temp[1] > interval[1]) {
                                    interval[1] = temp[1];
                                }
                            } else {
                                break;
                            }
                        }
                        i = --j;
                    }
                    flag = false;
                }
            }
            list.add(interval);
        }
        if (flag) {
            list.add(newInterval);
        }
        int[][] array = new int[list.size()][2];
        int i = 0;
        for (int[] ints : list) {
            array[i] = ints;
            i++;
        }
        return array;
    }

    public int lengthOfLastWord(String s) {
        char[] chars = s.toCharArray();
        boolean flag = true;
        int count = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (' ' == chars[i]) {
                if (flag) {
                    continue;
                } else {
                    break;
                }
            } else {
                flag = false;
                count++;
            }
        }
        return count;
    }

    public int[][] generateMatrix(int n) {
        int x = 0;
        int y = 0;
        int minX = 0;
        int minY = 0;
        int maxX = n - 1;
        int maxY = n - 1;
        int[][] array = new int[n][n];
        int num = 1;
        while (minX < maxX) {
            for (; x < maxX; x++) {
                array[y][x] = num++;
            }
            for (; y < maxY; y++) {
                array[y][x] = num++;
            }
            for (; x > minX; x--) {
                array[y][x] = num++;
            }
            for (; y > minY; y--) {
                array[y][x] = num++;
            }
            x++;
            y++;
            minX++;
            minY++;
            maxX--;
            maxY--;
        }
        if (minX == maxX) {
            array[y][x] = num++;
        }
        return array;
    }

    public String getPermutation(int n, int k) {

        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i + 1;
        }

        while (k > 1) {
            int sum = 1;
            int num = 1;
            while (sum < k) {
                num++;
                sum = sum * num;
            }
            int preSum = sum / num;

            int currentIndex = n - num;

            int step = (k - 1) / preSum;
            k = (k - 1) % preSum + 1;

            int temp = array[currentIndex + step];
            for (int i = currentIndex + step; i > currentIndex; i--) {
                array[i] = array[i - 1];
            }
            array[currentIndex] = temp;
        }

        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < array.length; i++) {
            buffer = buffer.append(array[i]);
        }
        return buffer.toString();
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        ListNode newHead = head;
        int count = 1;

        while (newHead.next != null) {
            count++;
            newHead = newHead.next;
        }
        int step = (count - k % count) % count;

        ListNode temp = head;
        ListNode pre = null;

        while (step > 0) {
            pre = temp;
            temp = temp.next;
            step--;
        }

        if (pre != null) {
            pre.next = null;
            newHead.next = head;
        }
        return temp;
    }

//    public int uniquePaths(int m, int n) {
//
//        if (m > n) {
//            int temp = m;
//            m = n;
//            n = temp;
//
//        }
//
//        return uniquePaths(m, n, 0);
//
//    }
//
//    public int uniquePaths(int m, int n, int mIndex) {
//
//        if (n == 1) {
//            return 1;
//        } else {
//            int sum = 0;
//            n--;
//            for (int i = mIndex; i < m; i++) {
//                sum += uniquePaths(m, n, i);
//            }
//            return sum;
//        }
//
//    }

    public int uniquePaths(int m, int n) {
        int[][] array = new int[m][n];
        for (int i = 0; i < n; i++) {
            array[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            array[i][0] = 1;
            for (int j = 1; j < n; j++) {
                array[i][j] = array[i][j - 1] + array[i - 1][j];
            }
        }
        return array[m - 1][n - 1];
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int first = obstacleGrid[0][0];
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                obstacleGrid[0][i] = 0;
                i++;
                for (; i < n; i++) {
                    obstacleGrid[0][i] = 0;
                }
            } else {
                obstacleGrid[0][i] = 1;
            }
        }
        obstacleGrid[0][0] = first;
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                obstacleGrid[i][0] = 0;
                i++;
                for (; i < m; i++) {
                    obstacleGrid[i][0] = 0;
                }
            } else {
                obstacleGrid[i][0] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i][j - 1] + obstacleGrid[i - 1][j];
                }
            }
        }
        return obstacleGrid[m - 1][n - 1];

    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 1; i < n; i++) {
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int min = grid[i][j - 1] < grid[i - 1][j] ? grid[i][j - 1] : grid[i - 1][j];
                grid[i][j] = min + grid[i][j];
            }
        }
        return grid[m - 1][n - 1];
    }

    public boolean isNumber(String s) {
        char[] charArray = s.toCharArray();

        if (charArray.length == 0) {
            return true;
        }

        int eIndex = -1;

        for (int i = 0; i < charArray.length; i++) {
            if ('e' == charArray[i] || 'E' == charArray[i]) {
                eIndex = i;
                break;
            }
        }
        if (eIndex > -1) {
            if (eIndex == 0 || eIndex == charArray.length - 1) {
                return false;
            }
            return bb(charArray, 0, eIndex - 1) && aa(charArray, eIndex + 1, charArray.length - 1);
        } else {
            return bb(charArray, 0, charArray.length - 1);
        }
    }

    boolean aa(char[] charArray, int start, int end) {

        for (int i = start; i <= end; i++) {
            if ('0' <= charArray[i] && charArray[i] <= '9') {
                continue;
            } else if ('-' == charArray[i] || '+' == charArray[i]) {
                if (i > start) {
                    return false;
                }
                if (start == end) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }

    boolean bb(char[] charArray, int start, int end) {

        for (int i = start; i <= end; i++) {
            if (('0' <= charArray[i] && charArray[i] <= '9') || '.' == charArray[i]) {
                if ('0' <= charArray[i] && charArray[i] <= '9') {
                    continue;
                } else {
                    if (end == i) {
                        if (i == start) {
                            return false;
                        } else if (charArray[i - 1] < '0' || charArray[i - 1] > '9') {
                            return false;
                        }
                    } else if (charArray[i + 1] < '0' || charArray[i + 1] > '9') {
                        if (i == start) {
                            return false;
                        } else if (charArray[i - 1] < '0' || charArray[i - 1] > '9') {
                            return false;
                        }
                    }
                    i++;
                    for (; i <= end; i++) {
                        if (charArray[i] < '0' || charArray[i] > '9') {
                            return false;
                        }
                    }

                }
            } else if ('-' == charArray[i] || '+' == charArray[i]) {
                if (i > start) {
                    return false;
                }
                if (start == end) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }

    public int[] plusOne(int[] digits) {

        int add = 1;

        for (int i = digits.length - 1; i >= 0; i--) {
            int temp = digits[i];
            digits[i] = (digits[i] + add) % 10;
            add = (temp + add) / 10;
        }
        if (add == 1) {
            int[] array = new int[digits.length + 1];
            array[0] = 1;
            for (int i = 0; i < digits.length; i++) {
                array[i + 1] = digits[i];
            }
            return array;
        } else {
            return digits;
        }

    }

    public String addBinary(String a, String b) {
        char[] charArrayA = a.toCharArray();
        char[] charArrayB = b.toCharArray();
        int indexA = charArrayA.length - 1;
        int indexB = charArrayB.length - 1;
        int add = 0;
        String s = "";
        while (indexA >= 0 && indexB >= 0) {
            int tempA = charArrayA[indexA] - '0';
            int tempB = charArrayB[indexB] - '0';

            if (add + tempA + tempB == 0) {
                add = 0;
                s = "0" + s;
            } else if (add + tempA + tempB == 1) {
                add = 0;
                s = "1" + s;
            } else if (add + tempA + tempB == 2) {
                add = 1;
                s = "0" + s;
            } else {
                add = 1;
                s = "1" + s;
            }
            indexA--;
            indexB--;
        }
        if (indexA >= 0) {
            while (indexA >= 0) {
                int tempA = charArrayA[indexA] - '0';
                if (add + tempA == 0) {
                    add = 0;
                    s = "0" + s;
                } else if (add + tempA == 1) {
                    add = 0;
                    s = "1" + s;
                } else {
                    add = 1;
                    s = "0" + s;
                }
                indexA--;
            }
        } else if (indexB >= 0) {
            while (indexB >= 0) {
                int tempB = charArrayB[indexB] - '0';
                if (add + tempB == 0) {
                    add = 0;
                    s = "0" + s;
                } else if (add + tempB == 1) {
                    add = 0;
                    s = "1" + s;
                } else {
                    add = 1;
                    s = "0" + s;
                }
                indexB--;
            }
        }
        if (add == 1) {
            s = "1" + s;
        }
        return s;
    }

    public List<String> fullJustify(String[] words, int maxWidth) {
        int count = 0;
        int index = 0;
        List<String> list = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (count + words[i].length() > maxWidth) {
                int piece = i - index;
                if (piece == 1) {
                    StringBuffer buffer = new StringBuffer(words[index]);
                    for (int j = 0; j < maxWidth - count + 1; j++) {
                        buffer.append(" ");
                    }
                    list.add(buffer.toString());
                } else {
                    int space = (maxWidth - count + piece) / (piece - 1);
                    int addNum = (maxWidth - count + piece) % (piece - 1);
                    StringBuffer buffer = new StringBuffer();
                    for (int j = index; j < i - 1; j++) {
                        buffer.append(words[j]);
                        for (int k = 0; k < space; k++) {
                            buffer.append(" ");
                        }
                        if (j - index < addNum) {
                            buffer.append(" ");
                        }
                    }
                    buffer.append(words[i - 1]);
                    list.add(buffer.toString());
                }
                index = i--;
                count = 0;
            } else {
                count += words[i].length() + 1;
            }
        }
        StringBuffer buffer = new StringBuffer();
        for (int i = index; i < words.length - 1; i++) {
            buffer.append(words[i]).append(" ");
        }
        buffer.append(words[words.length - 1]);
        for (int i = 0; i < maxWidth - count + 1; i++) {
            buffer.append(" ");
        }
        list.add(buffer.toString());
        return list;
    }

    public int mySqrt(int x) {
        if (x == 1) {
            return 1;
        }
        int min = 0;
        int max = x;
        while (max - min > 1) {
            int y = (max + min) / 2;
            if (x / y < y) {
                max = y;
            } else {
                min = y;
            }
        }
        return min;
    }

    public int climbStairs(int n) {

        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int step1 = 1;
        int step2 = 2;
        int i = 3;
        for (; i <= n; i = i + 2) {
            step1 = step1 + step2;
            step2 = step1 + step2;
        }
        if (i == n + 1) {
            return step2;
        } else {
            return step1;
        }

    }

    public String simplifyPath(String path) {
        String[] split = path.split("/");
        int length = split.length;
        int index = 0;
        for (int i = 0; i < length; i++) {
            if ("..".equals(split[i])) {
                if (index > 0) {
                    index--;
                }
                continue;
            } else if (".".equals(split[i]) || "".equals(split[i])) {
                continue;
            }
            split[index] = split[i];
            index++;
        }
        if (index == 0) {
            return "/";
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < index; i++) {
            builder.append("/").append(split[i]);
        }
        return builder.toString();
    }

    public int minDistance(String word1, String word2) {
        char[] charArray1 = word1.toCharArray();
        char[] charArray2 = word2.toCharArray();
        int length1 = charArray1.length;
        int length2 = charArray2.length;
        int[][] array = new int[length1 + 1][length2 + 1];
        int shortLength = length1 < length2 ? length1 : length2;
        for (int i = 0; i < shortLength; i++) {
            array[i][0] = i;
            array[0][i] = i;
        }
        if (length1 == shortLength) {
            for (int i = shortLength; i < length2 + 1; i++) {
                array[0][i] = i;
            }
        } else {
            for (int i = shortLength; i < length1 + 1; i++) {
                array[i][0] = i;
            }
        }
        for (int i = 1; i < length2 + 1; i++) {
            for (int j = 1; j < length1 + 1; j++) {
                int a = array[j - 1][i] + 1;
                int b = array[j][i - 1] + 1;
                int c = array[j - 1][i - 1];
                if (charArray2[i - 1] != charArray1[j - 1]) {
                    c++;
                }
                int min = a < b ? a : b;
                min = min < c ? min : c;
                array[j][i] = min;
            }
        }
        return array[length1][length2];
    }

    public void setZeroes(int[][] matrix) {
        int lengthY = matrix.length;
        int lengthX = matrix[0].length;
        boolean flagX = false;
        boolean flagY = false;
        for (int i = 1; i < lengthY; i++) {
            if (matrix[i][0] == 0) {
                flagY = true;
                break;
            }
        }
        for (int i = 1; i < lengthX; i++) {
            if (matrix[0][i] == 0) {
                flagX = true;
                break;
            }
        }
        for (int i = 1; i < lengthY; i++) {
            for (int j = 1; j < lengthX; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < lengthY; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < lengthX; j++) {
                    if (matrix[i][j] != 0) {
                        matrix[i][j] = 0;
                    }
                }
            }
        }
        for (int i = 1; i < lengthX; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 1; j < lengthY; j++) {
                    if (matrix[j][i] != 0) {
                        matrix[j][i] = 0;
                    }
                }
            }
        }
        boolean flagFirst = matrix[0][0] == 0;
        if (flagFirst || flagX) {
            for (int j = 0; j < lengthX; j++) {
                if (matrix[0][j] != 0) {
                    matrix[0][j] = 0;
                }
            }
        }
        if (flagFirst || flagY) {
            for (int j = 0; j < lengthY; j++) {
                if (matrix[j][0] != 0) {
                    matrix[j][0] = 0;
                }
            }
        }
    }

    public boolean searchMatrix(int[][] matrix, int target) {

        int lengthY = matrix.length;

        int lengthX = matrix[0].length;

        for (int i = 0; i < lengthY; i++) {
            if (matrix[i][0] > target) {
                if (i == 0) {
                    return false;
                }
                for (int j = 0; j < lengthX; j++) {
                    if (matrix[i - 1][j] == target) {
                        return true;
                    }
                    if (matrix[i - 1][j] > target) {
                        return false;
                    }
                }
                return false;
            }
        }
        for (int j = 0; j < lengthX; j++) {
            if (matrix[lengthY - 1][j] == target) {
                return true;
            }
            if (matrix[lengthY - 1][j] > target) {
                return false;
            }
        }
        return false;
    }

    public void sortColors(int[] nums) {

        int i = 0;
        int start = 0;
        int end = nums.length - 1;
        while (i <= end) {
            while (start < nums.length - 1 && nums[start] == 0) {
                start++;
            }
            if (start == nums.length) {
                break;
            }
            while (end > -1 && nums[end] == 2) {
                end--;
            }
            if (end == -1) {
                break;
            }
            if (start >= end) {
                break;
            }
            if (i < start) {
                i = start;
            }
            if (nums[i] == 0) {
                int temp = nums[start];
                nums[start] = 0;
                nums[i] = temp;
                i++;
            } else if (nums[i] == 2) {
                int temp = nums[end];
                nums[end] = 2;
                nums[i] = temp;
            } else {
                i++;
            }
        }
    }

    public String minWindow(String s, String t) {

        char[] charArray = t.toCharArray();
        int length = charArray.length;
        int[] array = new int[length];
        for (int i = 0; i < length; i++) {
            array[i] = -1;
        }
        char[] sourceArray = s.toCharArray();
        int minWindow = -1;
        int startIndex = -1;
        int endIndex = -1;
        for (int i = 0; i < sourceArray.length; i++) {
            char c = sourceArray[i];
            for (int j = 0; j < length; j++) {
                if (c == charArray[j]) {
                    int temp = array[j];
                    array[j] = i;
                    if (temp != -1) {
                        for (int k = j; k < length; k++) {
                            if (c == charArray[k]) {
                                int temp1 = array[k];
                                if (temp1 != -1) {
                                    if (temp1 < temp) {
                                        array[k] = temp;
                                        temp = temp1;
                                    }
                                } else {
                                    array[k] = temp;
                                    break;
                                }
                            }
                        }
                    }

                    int minIndex = array[0];
                    for (int k = 1; k < length; k++) {
                        minIndex = minIndex < array[k] ? minIndex : array[k];
                    }
                    if (minIndex != -1) {
                        int tempMin = i - minIndex;
                        if (minWindow != -1) {
                            if (tempMin < minWindow) {
                                minWindow = tempMin;
                                startIndex = minIndex;
                                endIndex = i;
                            }
                        } else {
                            minWindow = tempMin;
                            startIndex = minIndex;
                            endIndex = i;
                        }
                    }
                    break;
                }
            }
        }

        if (minWindow == -1) {
            return "";
        } else {
            return String.valueOf(sourceArray, startIndex, endIndex - startIndex + 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {

        int[] array = new int[k];
        List<List<Integer>> list = new ArrayList<>();
        combine1(1, n - k + 1, k, array, list);
        return list;
    }

    public void combine1(int m, int n, int k, int[] array, List<List<Integer>> list) {
        for (int i = m; i <= n; i++) {
            array[k - 1] = i;
            if (k > 1) {
                combine1(i + 1, n + 1, k - 1, array, list);
            } else {
                List<Integer> integerArrayList = new ArrayList<>();
                for (int j = array.length - 1; j >= 0; j--) {
                    integerArrayList.add(array[j]);
                }
                list.add(integerArrayList);
            }
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int[] array = new int[i + 1];
            subsets1(0, nums.length - 1 - i, nums, i + 1, array, list);
        }
        List<Integer> integerList = new ArrayList<>();
        list.add(integerList);
        return list;
    }

    public void subsets1(int m, int n, int[] nums, int k, int[] array, List<List<Integer>> list) {
        for (int i = m; i <= n; i++) {
            array[k - 1] = nums[i];
            if (k > 1) {
                subsets1(i + 1, n + 1, nums, k - 1, array, list);
            } else {
                List<Integer> integerArrayList = new ArrayList<>();
                for (int j = array.length - 1; j >= 0; j--) {
                    integerArrayList.add(array[j]);
                }
                list.add(integerArrayList);
            }
        }
    }

    public boolean exist(char[][] board, String word) {
        return false;
    }


    public int maximalRectangle(char[][] matrix) {

        int lengthY = matrix.length;

        if (lengthY == 0) {
            return 0;
        }
        int lengthX = matrix[0].length;

        int[][] array = new int[lengthY][lengthX];
        int max = 0;

        for (int i = 0; i < lengthY; i++) {
            for (int j = 0; j < lengthX; j++) {
                char c = matrix[i][j];
                if (c == '0') {
                    array[i][j] = 0;
                } else {
                    if (j == 0) {
                        array[i][j] = 1;
                    } else {
                        array[i][j] = array[i][j - 1] + 1;
                    }
                    int xMin = array[i][j];
                    max = max > xMin ? max : xMin;
                    for (int k = i - 1; k >= 0; k--) {
                        int tempXMin = array[k][j];
                        if (tempXMin == 0) {
                            break;
                        }
                        xMin = xMin < tempXMin ? xMin : tempXMin;
                        max = max > xMin * (i - k + 1) ? max : xMin * (i - k + 1);
                    }
                }
            }
        }
        return max;
    }

    public int lengthOfLongestSubstring(String s) {

        if (s.length() <= 1) {
            return s.length();
        }

        // 当前前方无重复节点
        int startIndex = 0;
        int maxLength = 0;
        Map<Character, Integer> map = new HashMap<>();

        char[] charArray = s.toCharArray();

        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            Integer index = map.get(c);
            //
            if (index == null || index < startIndex) {
                int tempLength = i - startIndex + 1;
                if (maxLength < tempLength) {
                    maxLength = tempLength;
                }
            } else {
                int tempLength = i - index;
                if (maxLength < tempLength) {
                    maxLength = tempLength;
                }
                startIndex = index + 1;
            }
            map.put(c, i);
        }
        return maxLength;

    }

    public String intToRoman1(int num) {

        int len = 0;
        String result = "";
        String[][] array = {{"I", "V"}, {"X", "L"}, {"C", "D"}, {"M"}};
        while (num > 0) {
            int more = num % 10;
            if (more < 4) {
                while (more > 0) {
                    result = array[len][0] + result;
                    more--;
                }
            } else if (more == 4) {
                result = array[len][0] + array[len][1] + result;
            } else if (more == 5) {
                result = array[len][1] + result;
            } else if (more < 9) {
                more = more - 5;
                String temp = array[len][1];
                while (more > 0) {
                    temp = temp + array[len][0];
                    more--;
                }
                result = temp + result;
            } else {
                result = array[len][0] + array[len + 1][0] + result;
            }
            num = num / 10;
            len++;
        }
        return result;

    }

    public int divide1(int dividend, int divisor) {

        int maxValue = 2147483647;
        int minValue = -2147483648;
        if (dividend == minValue && divisor == -1) {
            return maxValue;
        }
        if (dividend == minValue && divisor == minValue) {
            return 1;
        }
        if (dividend > minValue && divisor == minValue) {
            return 0;
        }
        int ratio = 1;
        int add = 0;
        if (dividend < 0) {
            if (dividend == minValue) {
                dividend = maxValue;
                add = 1;
            } else {
                dividend = -dividend;
            }

            ratio = -ratio;
        }
        if (divisor < 0) {
            divisor = -divisor;
            ratio = -ratio;
        }

        int count = 0;

        while (dividend - divisor >= -add) {
            int countCurrent = 0;
            int countAdd = 1;
            int divisorCurrent = 0;
            int divisorAdd = divisor;

            while (dividend - divisorAdd >= -add) {
                countCurrent = countAdd;
                divisorCurrent = divisorAdd;
                if (maxValue - divisorAdd < divisorAdd) {
                    break;
                }
                divisorAdd = divisorAdd + divisorAdd;
                countAdd = countAdd + countAdd;
            }
            count = count + countCurrent;
            dividend = dividend - divisorCurrent;
        }
        if (ratio == -1) {
            count = -count;
        }

        return count;
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        Arrays.sort(candidates);

        List<List<Integer>> resultList = new ArrayList<>();

        combination(candidates, 0, null, target, resultList);

        return resultList;

    }

    public void combination(int[] candidates, int index, List<Integer> list, int target, List<List<Integer>> resultList) {
        if (list != null) {
            int sum = 0;
            for (Integer integer : list) {
                sum += integer;
            }
            if (sum == target) {
                resultList.add(list);
                return;
            }
            if (sum > target) {
                return;
            }
        }

        Integer sign = null;
        for (int i = index; i < candidates.length; i++) {
            int candidate = candidates[i];
            if (sign == null || sign != candidate) {
                sign = candidate;
                List<Integer> nextList = new ArrayList<>();
                if (list != null) {
                    nextList.addAll(list);
                }
                nextList.add(candidate);
                combination(candidates, i + 1, nextList, target, resultList);
            } else {
                continue;
            }

        }
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);

        List<List<Integer>> resultList = new ArrayList<>();

        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                for (int k = j + 1; k < nums.length - 1; k++) {
                    if (k > j + 1 && nums[k] == nums[k - 1]) {
                        continue;
                    }
                    for (int l = k + 1; l < nums.length; l++) {
                        if (l > k + 1 && nums[l] == nums[l - 1]) {
                            continue;
                        }
                        if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                            List<Integer> list = new ArrayList<>();
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[k]);
                            list.add(nums[l]);
                            resultList.add(list);
                            break;
                        }
                    }
                }
            }
        }

        return resultList;
    }

    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (nums[nums.length - 1] < 0) {
                break;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            for (int j = i + 1; j < nums.length - 1; j++) {
                if (nums[i] + nums[j] > 0) {
                    break;
                }
                if (nums[i] + nums[j] + nums[nums.length - 1] < 0) {
                    continue;
                }
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] > 0) {
                        break;
                    }
                    if (k > j + 1 && nums[k - 1] == nums[k]) {
                        continue;
                    }
                    if (nums[i] + nums[j] + nums[k] == 0) {

                        List<Integer> integerList = new ArrayList<>();
                        integerList.add(nums[i]);
                        integerList.add(nums[j]);
                        integerList.add(nums[k]);
                        list.add(integerList);
                    }
                }
            }
        }
        return list;
    }

    public int leastOpsExpressTarget(int x, int target) {

        int count = 0;


        while (target >= x) {
            int currentCount = 0;
            int currentX = 0;
            int nextCount = 1;
            int nextX = x;
            while (target >= nextX) {
                currentCount = nextCount;
                currentX = nextX;

                nextX = nextX * x;
                nextCount++;
            }
            count = count + currentCount;
            target = target - currentX;
        }

        int tail1 = 2 * target;
        int other = x - target;
        int tail2 = 2 * other + 1;

        int minTail = tail1 < tail2 ? tail1 : tail2;


        return count + minTail - 1;
    }

}
